#ifndef _MINSTACK_
#define _MINSTACK_
#include <stack>
#include <vector>
using namespace std;
class MinStack {
public:
    /** initialize your data structure here. */
    struct ListNode {
        int       data;
        int       min;
        ListNode* front;
        ListNode* next;
    };

    MinStack() {
        _head = _tail = nullptr;
    }

    void push( int x ) {
        ListNode* temp = new ListNode();
        temp->data = temp->min = x;
        temp->front = temp->next = temp;

        if ( _head == nullptr ) {
            _head = _tail = temp;
        }
        else {
            if ( _tail->min < x ) {
                temp->min = _tail->min;
            }

            _tail->next = temp;
            temp->front = _tail;
            _tail       = temp;

            _head->front = _tail;
            _tail->next  = _head;
        }
    }

    void pop() {
        if ( _head == nullptr ) {
            return;
        }
        if ( _head == _tail ) {
            _head = _tail = nullptr;
            return;
        }

        ListNode* temp = _tail;
        _tail          = _tail->front;
        _head->front   = _tail;
        _tail->next    = _head;
        delete temp;
    }

    int top() {

        if ( _tail != nullptr ) {
            return _tail->data;
        }
        return -1;
    }

    int min() {
        if ( _head != nullptr ) {
            return _tail->min;
        }
        return -1;
    }

private:
    ListNode* _head;
    ListNode* _tail;
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->min();
 */
class AboutStack {

public:
    AboutStack( /* args */ ) {}
    ~AboutStack() {}
    /*输入入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。
    例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列*/
    bool validateStackSequences( vector< int >& pushed, vector< int >& popped ) {
       int lenPush = pushed.size(); 
        int lenPop=popped.size();
       
        if ( lenPop < 0 || lenPush < 0 ||  lenPop != lenPush ) {
            return false;
        }

        stack< int > tempStack;
        int          j = 0;
        for ( int i = 0; i < lenPush; i++ ) {
            tempStack.push( pushed[ i ] );
            while ( j < lenPop && tempStack.top() == popped[ j ] ) {
                tempStack.pop();
                j++;
            }
        }

        return tempStack.empty();
    }

private:
    /* data */
};

#endif /*_MINSTACK_*/